#coding = utf-8
import numpy as np
import cv2

#求从任意两组点中间切开，不切到板，且到最近两点距离距离最远的切线
#每组点不要求数量

def calc_middle_line(pas,pbs):
    good_lines = []
    good_lines_k = []
    # good_lines_r = []
    # line_r = []
    # line_ur = []
    #求出最极限的两根切线
    ps_out = [*pas,*pbs]
    ps_in = [*pas,*pbs]
    # back = np.zeros((5000,5000,3),dtype="uint8")
    # back_1 = np.zeros((5000,5000,3),dtype="uint8")
    # for p in pas:
    #     cv2.circle(back, tuple(p), 3, (0, 255, 0), 3)
    #     cv2.circle(back_1, tuple(p), 3, (0, 255, 0), 3)
    # for p in pbs:
    #     cv2.circle(back, tuple(p), 3, (255, 0, 0), 3)
    #     cv2.circle(back_1, tuple(p), 3, (255, 0, 0), 3)
    for p0 in ps_out:
        for p1 in ps_in:
            if p0[0] == p1[0] and p0[1] == p1[1]:
                continue
            k,b = get_line_by_p(p0,p1)
            # if k is not None:
            #     cv2.line(back,(0,int(b)),(5000,int(5000*k+b)),(0,0,255),3)
            # else:
            #     cv2.line(back, (b, 0), (b, 5000), (0, 0, 255), 3)
            # cv2.namedWindow("res",cv2.WINDOW_KEEPRATIO)
            # cv2.imshow("res", back)
            # cv2.waitKey(1)
            # 不能把p0,p1传进去
            pas_remove = pas.copy()
            pbs_remove = pbs.copy()
            try:
                pas_remove.remove(p0)
            except:
                pass
            try:
                pas_remove.remove(p1)
            except:
                pass
            try:
                pbs_remove.remove(p0)
            except:
                pass
            try:
                pbs_remove.remove(p1)
            except:
                pass
            if check_validity(pas_remove,pbs_remove,k,b):
                good_lines.append([k,b])
                good_lines_k.append(k)
        ps_in.remove(p0)


    if len(good_lines) == 0:
        return None,None
    elif len(good_lines) == 1:
        return good_lines[0]
    elif len(good_lines) > 1:
        res_lines = []
        projections = []
        lines_1 = good_lines.copy()
        lines_2 = good_lines.copy()
        #直接求每两条线的中分线
        for line_1 in lines_1:
            for line_2 in lines_2:
                if line_1 == line_2:
                    continue
                #求两条中分线 要考虑None
                if line_1[0] is None:
                    ang_1 = 90
                else:
                    ang_1 = np.arctan(line_1[0]) * 180 / np.pi

                if line_2[0] is None:
                    ang_2 = 90
                else:
                    ang_2 = np.arctan(line_2[0]) * 180 / np.pi

                best_a_1 = (ang_1 + ang_2)/2

                if best_a_1 > 0:
                    best_a_2 = best_a_1 - 90
                else:
                    best_a_2 = best_a_1 + 90

                for best_a in [best_a_1,best_a_2]:
                    if abs(best_a) != 90:
                        best_k = np.tan(best_a*np.pi/180)
                    else:
                        best_k = None

                    #求垂线的k,变换之后仍要在±90度，如果正角度减90，如果负角度减90
                    if best_a>0:
                        vertical_a = best_a - 90
                    else:
                        vertical_a = best_a + 90

                    #求b，线应该过在k垂线方向上，投影最短的两点，连线的中点
                    #求出，两组任意两点的组合集合
                    pps = []
                    for p0 in pas:
                        for p1 in pbs:
                            pps.append([p0,p1])

                    #求每个组合的线段在-1/k向量上的投影，找到最短的一组
                    ang_s = []
                    ##求每组的角度
                    for pc in pps:
                        k = get_line_k(pc[0],pc[1])
                        if k is not None:
                            ang_s.append(np.arctan(k)*180/np.pi)
                        else:
                            ang_s.append(90)

                    ##求两个向量夹的锐角,0-90,应该用180度去减两角绝对值和
                    ang_sub_s = []
                    for ang in ang_s:
                        ang_sub = abs(vertical_a-ang)
                        if ang_sub>90:
                            ang_sub = 180 - ang_sub
                        ang_sub_s.append(ang_sub)

                    #求过最短一组连线中点，斜率为k的线的b值
                    ##求每组的距离
                    distances = [distance(ps[0],ps[1]) for ps in pps]
                    projection = [np.cos(ang_sub_s[i]*np.pi/180)*distances[i] for i in range(len(pps))]
                    ##求最小组
                    min_index = projection.index(min(projection))
                    pp = pps[min_index]

                    ##中点
                    pp_mid = [(pp[0][0]+pp[1][0])/2,(pp[0][1]+pp[1][1])/2]

                    ##求b
                    if best_k is None:
                        b = pp_mid[0]
                    else:
                        b = pp_mid[1] - best_k * pp_mid[0]
                    if check_validity(pas,pbs,best_k,b):
                        res_lines.append([best_k,b])
                        projections.append(min(projection))
            lines_2.remove(line_1)
        #求投影最大的一组
        res = None,None
        try:
            res = res_lines[projections.index(max(projections))]
        except:
            pass
        # k, b = res
        # if k:
        #     cv2.line(back_1, (0, int(b)), (5000, int(5000 * k + b)), (255, 255, 255), 3)
        # else:
        #     cv2.line(back_1, (int(b), 0), (int(b), 5000), (255, 255, 255), 3)
        # cv2.namedWindow("res1", cv2.WINDOW_KEEPRATIO)
        # cv2.imshow("res1", back_1)
        # # cv2.imwrite("slkdfj.jpg",back_1)
        # cv2.waitKey(0)
        return res



def check_rotate(p0,p1,k,b,pas,pbs):
    #求两点中点
    # p_mid = [(p0[0]+p1[0])/2,(p0[1]+p1[1])/2]
    if k is not None:
        #顺时针k变小
        k_r = k - 0.001
        #逆时针k变大
        k_ur = k + 0.001
    else:
        k_r = np.tan((90-0.001)*np.pi/180)
        k_ur = np.tan((-90 + 0.001) * np.pi / 180)
    #求b
    b_r = p0[1] - k_r * p0[0]
    b_ur = p0[1] - k_ur * p0[0]

    pas_remove = pas.copy()
    pbs_remove = pbs.copy()
    try:
        pas_remove.remove(p0)
    except:
        pass
    try:
        pbs_remove.remove(p1)
    except:
        pass

    #检查是否能通过
    res_r = check_validity(pas_remove,pbs_remove,k_r,b_r)
    res_ur = check_validity(pas_remove,pbs_remove,k_ur,b_ur)
    if not res_r and not res_ur:
        return "no"
    elif res_r:
        return "r"
    elif res_ur:
        return "ur"
    else:
        return "err"

def distance(p1,p2):
    assert len(p1)==2
    assert len(p2)==2
    return np.sqrt((abs(p2[0]-p1[0])**2+abs(p2[1]-p1[1])**2))

def check_validity(pas,pbs,k,b):
    #检查线是否分开了每个点
    #利用线的斜率和pas，pbs里面的点构成一条新的线，判断同一组的b是否都大于等于（或小于等于）原来的b
    #k
    bas = []
    bbs = []
    if k is not None:
        for p in pas:
            bas.append(p[1]-k*p[0])
        for p in pbs:
            bbs.append(p[1]-k*p[0])
    else:
        #x=b 直接比较x就可以了
        for p in pas:
            bas.append(p[0])
        for p in pbs:
            bbs.append(p[0])
    bas = np.array(bas)
    bbs = np.array(bbs)
    res_a = bas>=b
    res_b = bbs>=b
    #当一组全部为0，一组全部为1时返回真
    if (np.sum(res_a) == 0 and np.sum(res_b) == len(res_b)) or (np.sum(res_b) == 0 and np.sum(res_a) == len(res_a)):
        return True
    return False

def get_line_by_p(p0,p1):
    #通过两个点求直线
    k = get_line_k(p0, p1)
    if k is None:
        # 垂直，x = b
        b = p0[0]
    else:
        b = p0[1] -  k * p0[0]
    return k,b

def get_line_k(p1,p2):
    if p1[0] == p2[0]:
        #垂直于x轴，没有K值
        return None
    else:
        return (p2[1] - p1[1])*1.0/(p2[0] - p1[0])

if __name__ == "__main__":
    import random

    max_xy = 6000
    for i in range(1):
        back = np.zeros((max_xy,max_xy,3),dtype="uint8")
        back_1 = np.zeros((max_xy, max_xy, 3), dtype="uint8")
        # pas = [(120,160),(100,290),(100,390),(90,450),(130,790),(150,850)]
        # pbs = [(180,200),(190,710),(200,810)]
        # pas = [(120,190),(200,190),(300,190)]
        # pbs = [(120,300),(200,300),(300,300)]
        pas = [(2207,   77),(2209, 1675),(2202, 1748),(2196, 3345)]
        pbs = [(2380,   28),(2348, 1622),(2381, 1677),(2350, 3270)]
        # for i in range(4):
        #     pas.append((random.randint(0,max_xy),random.randint(0,max_xy)))
        #     pbs.append((random.randint(0, max_xy), random.randint(0, max_xy)))


        for p in pas:
            cv2.circle(back,p,3,(0,255,0),3)
            cv2.circle(back_1, p, 3, (0, 255, 0), 3)
        for p in pbs:
            cv2.circle(back,p,3,(255,0,0),3)
            cv2.circle(back_1, p, 3, (255, 0, 0), 3)
        cv2.namedWindow("res",cv2.WINDOW_KEEPRATIO)
        cv2.imshow("res",back)
        cv2.waitKey(1)
        try:
            line = calc_middle_line(pas, pbs)
            print(line)
            k, b = line
            if k:
                cv2.line(back_1,(0,int(b)),(max_xy,int(max_xy*k+b)),(255,255,255),3)
            else:
                cv2.line(back_1, (int(b), 0), (int(b), max_xy), (255, 255, 255), 3)
            cv2.namedWindow("res1", cv2.WINDOW_KEEPRATIO)
            cv2.imshow("res1", back_1)
            cv2.waitKey(0)
        except Exception as e:
            print("Dont have cut line ：",e)
